IOI 2022 Day 1 P2 Prisoner Challenge¶

Problem¶

Problem Link¶

https://www.acmicpc.net/problem/25439
https://oj.uz/problem/view/IOI22_prison

Summary¶

\(500\)명의 죄수가 있고, 방 안에는 가방 \(A\), \(B\)와 \(0\) 이상 \(x\)이하의 수를 적을 수 있는 칠판 하나가 있다. 가방 \(A\), \(B\)에는 \(1\)개 이상, \(N\)개 이하의 서로 다른 개수의 동전들이 들어 있고, 죄수들은 두 가방 중 어떤 가방에 동전이 더 적게 들어 있는지 맞추어야 한다.
죄수들은 한 명씩, 칠판에 적혀 있는 수를 본 후 가방 \(A\), \(B\) 중 하나를 골라 이 가방의 동전의 수를 확인한 후, 칠판에 있던 수를 지우고 자기가 원하는 수를 적거나, 두 가방 중 어떤 가방에 동전이 더 적게 들어있는지 맞출 수 있다. 이 때 잘못된 가방을 선택하면 안되고, 각 죄수는 칠판에 써있는 정보 이외의 다른 정보(자신이 몇 번째로 들어왔는지 등)는 얻을 수 없다.
이 때, \(x\)를 최소화시킬 수 있는 전략을 구하여라.

Constraints¶

\(2 \le N \le 5,000\)
\(x \le 20\) (\(x\)의 최대 크기에 따라 부분 점수를 얻을 수 있다.)

Solution¶

Subtask 1¶

\(N \le 500\)
\(x \le 500\)

다음과 같은 전략으로 문제를 해결할 수 있다.

첫 번째 사람은 칠판에 \(0\)이 써있으니, 가방 \(A\)를 열어보고 그 동전의 수를 칠판에 적는다.
두 번째 사람은 칠판에 \(0\)이 아닌 수가 써있으니, 가방 \(B\)를 열어보고 칠판의 수와 비교하여 답을 구한다.

CheckPoint

다음과 같은 전략으로 문제를 해결할 수 있다.

첫 번째 사람은 칠판에 \(0\)이 써있으니, 가방 \(A\)를 열어보고 그 동전의 수를 칠판에 적는다.
두 번째 사람은 칠판에 \(0\)이 아닌 수가 써있으니, 가방 \(B\)를 열어보고 칠판의 수와 비교하여 답을 구한다.

Subtask 3.1¶

\(N \le 5000\)
\(x \le 26\)

기본적으로 두 수를 비교하는 문제이니, 2진수로 나타내 가장 높은 비트부터 하나씩 비교하는 전략을 생각할 수 있다.

첫 번째 사람은 칠판에 \(0\)이 써있으니, 가방 \(A\)를 열어보고 \(12\)번째 비트를 확인하여 \(1\), \(2\)중 하나의 수를 칠판에 적는다.
두 번째 사람은 적혀 있는 \(1\), \(2\)중 하나의 수를 읽고 가방 \(B\)를 열어보고 \(12\)번째 비트를 확인하여 칠판에 적혀있는 정보인 \(A\)의 \(12\)번째 비트와 비교한 후 다르면 답을 맞추고, 같다면 \(B\)의 \(11\)번째 비트를 확인하여 \(3\), \(4\)중 하나의 수를 칠판에 적는다.
위 과정을 반복하여 마지막 비트까지 비교한다.

이 전략을 사용하면 \(0\)번째 비트에 대한 정보가 적힌 칠판을 확인하는 순간 답을 결정할 수 있으며, 따라서 총 \(13\)개의 비트에 대하여 \(0\)부터 \(26\)까지의 상태로 나타낼 수 있다.

CheckPoint

2진수로 나타내 가장 높은 비트부터 하나씩 비교하는 전략을 사용한다.

첫 번째 사람은 칠판에 \(0\)이 써있으니, 가방 \(A\)를 열어보고 \(12\)번째 비트를 확인하여 \(1\), \(2\)중 하나의 수를 칠판에 적는다.
두 번째 사람은 적혀 있는 \(1\), \(2\)중 하나의 수를 읽고 가방 \(B\)를 열어보고 \(12\)번째 비트를 확인하여 칠판에 적혀있는 정보인 \(A\)의 \(12\)번째 비트와 비교한 후 다르면 답을 맞추고, 같다면 \(B\)의 \(11\)번째 비트를 확인하여 \(3\), \(4\)중 하나의 수를 칠판에 적는다.
위 과정을 반복하여 마지막 비트까지 비교한다.

이 전략을 사용하면 \(0\)번째 비트에 대한 정보가 적힌 칠판을 확인하는 순간 답을 결정할 수 있으며, 따라서 총 \(13\)개의 비트에 대하여 \(0\)부터 \(26\)까지의 상태로 나타낼 수 있다.

Subtask 3.2¶

\(N \le 5000\)
\(x \le 22\)

위 전략으로 56점 정도를 맞을 수 있으니, 큰 전략의 수정 없이 위 전략을 최적화할 수 있는 방법에 대해 생각하자.

우선, 꼭 수를 2진수로 표현할 필요가 없다. 3진수나 4진수, 혹은 각 자리수별로 가능한 수가 서로 다른 형태의 진법이 모두 가능하다. Subtask 3.1 전략의 핵심은, 각 단계에서 가능한 수의 범위를 적당히 쪼개 가방 \(A\) 혹은 \(B\)의 동전의 수가 특정 구간에 포함된다는 것을 최소한의 상태로 표현하는 것이다. 현재 칠판에 적혀 있는 정보로 가방 \(A\)가 구간 \([l, r]\)에 속한다는 정보를 얻었을 때, 가방 \(B\)가 구간에 속하지 않는다면 바로 답을 구할 수 있고, 구간에 속한다면 구간 \([l, r]\)을 \([l', r']\)으로 쪼개 새로운 상태로 칠판에 적으면 된다.

Observation 1

Subtask 3.1 전략의 핵심은, 각 단계에서 가능한 수의 범위를 적당히 쪼개 가방 \(A\) 혹은 \(B\)의 동전의 수가 특정 구간에 포함된다는 것을 최소한의 상태로 표현하는 것이다. 현재 칠판에 적혀 있는 정보로 가방 \(A\)가 구간 \([l, r]\)에 속한다는 정보를 얻었을 때, 가방 \(B\)가 구간에 속하지 않는다면 바로 답을 구할 수 있고, 구간에 속한다면 구간 \([l, r]\)을 \([l', r']\)으로 쪼개 새로운 상태로 칠판에 적으면 된다.

따라서 꼭 2진법이 가장 효율적인 것은 아니니 DP를 통해 최적의 분할 전략을 구할 수 있다. 구간을 최대한 고르게 나누는 것이 이득이니, 각 구간의 길이에 대하여 몇 개의 구간으로 쪼갤 것인지를 DP를 통해 구하면 된다.

Definition 1

\(dp[i] :=\) 구간의 길이가 \(i\)일 때 필요한 상태의 개수

\(\displaystyle dp[i] = \min_{j<i} {dp \left[ \left \lceil \frac{i}{j} \right \rceil \right] + j}\) 와 같은 점화식을 통해 구할 수 있다.

위 Definition 1와 같은 DP를 통해 \(N \le 5000\)에 대한 최적의 분할을 구하면 된다. 이 때, 마지막에 칠판에 어떤 수가 길이 \(2\)의 구간에 속한다는 것을 알 수 있다면, 더 이상 구간을 쪼개지 말고 가방을 한번 열어보았을 때 바로 답을 구할 수 있다. 이는 두 수가 서로 다르다는 조건 때문인데, 이를 이용하면 \(22\)개의 상태로 답을 구할 수 있다.

CheckPoint

Observation 1과 같이 칠판에 동전이 포함된 범위를 나타내는 상태를 적으면, 이 구간을 반복적으로 분할하며 문제를 해결할 수 있다. 이 때, 최적의 분할 전략을 구하기 위하여 Definition 1과 같은 DP를 이용할 수 있다. 추가로 마지막에 칠판에 어떤 수가 길이 \(2\)의 구간에 속한다는 것을 알 수 있다면, 더 이상 구간을 쪼개지 말고 가방을 한번 열어보았을 때 바로 답을 구할 수 있다. 이는 두 수가 서로 다르다는 조건 때문인데, 이를 이용하면 \(22\)개의 상태로 답을 구할 수 있다.

Subtask 3 (Full)¶

\(N \le 5000\)
\(x \le 20\)

Subtask 3.2의 마지막 부분에서 칠판에 어떤 수가 길이 \(2\)의 구간에 속한다는 것을 알 수 있다면, 더 이상 구간을 쪼개지 말고 가방을 한번 열어보았을 때 바로 답을 구할 수 있다는 점을 이용하였다. 이를 응용하여, 현재 칠판에 적혀 있는 정보로 가방 \(A\)가 구간 \([l, r]\)에 속한다는 정보를 얻었을 때, 가방 \(B\)가 정확히 \(l\)이나 \(r\)이라면 두 수가 서로 다르다는 조건을 이용하여 바로 답을 구할 수 있다. 이는, 사실 구간이 원래 \([l, r]\)이었다면, 다음 단계에서는 구간 \([l+1, r-1]\)을 여러 개의 작은 구간 \([l', r']\)으로 쪼개면 됨을 의미한다.

Observation 2

현재 칠판에 적혀 있는 정보로 가방 \(A\)가 구간 \([l, r]\)에 속한다는 정보를 얻었을 때, 가방 \(B\)가 정확히 \(l\)이나 \(r\)이라면 두 수가 서로 다르다는 조건을 이용하여 바로 답을 구할 수 있다. 이는, 사실 구간이 원래 \([l, r]\)이었다면, 다음 단계에서는 구간 \([l+1, r-1]\)을 여러 개의 작은 구간 \([l', r']\)으로 쪼개면 됨을 의미한다.

Observation 2을 이용하여 Definition 1의 DP를 수정하자.

Definition 2

\(dp[i] :=\) 구간의 길이가 \(i\)일 때 필요한 상태의 개수

\(\displaystyle dp[i] = \min_{j<i} {dp \left[ \left \lceil \frac{i-2}{j} \right \rceil \right] + j}\) 와 같은 점화식을 통해 구할 수 있다.

위 Definition 2와 같은 DP를 통해 최적의 분할 전략을 구하면, \(\{2, 3, 3, 3, 3, 2, 2, 2\}\)과 같은 순서로 분할을 진행하면, \(N=5022\)에 대하여 정확히 \(20\)개의 상태로 답을 구할 수 있다.

최종 풀이에서는 DP는 돌릴 필요 없이, 미리 계산된 배열 \(\{2, 3, 3, 3, 3, 2, 2, 2\}\)을 이용하여 전략을 구현하면 된다.

CheckPoint

Observation 2와 같이, 칠판에 적힌 구간 \([l, r]\)을 확인할 때마다 다음 단계에서는 구간 \([l+1, r-1]\)을 여러 개의 작은 구간 \([l', r']\)으로 쪼갤 수 있다. 이를 이용하여 Definition 2와 같은 DP를 통해 최적의 분할 전략을 구하면, \(\{2, 3, 3, 3, 3, 2, 2, 2\}\)과 같은 순서로 분할을 진행하면, \(N=5022\)에 대하여 정확히 \(20\)개의 상태로 답을 구할 수 있다.

Code¶

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int P[]={0, 2, 3, 3, 3, 3, 2, 2, 2};
int Q[]={0, 2, 5, 8, 11, 14, 16, 18, 20};
int A[21][5023];
int B[10][5023];

void f(int pos, int l, int r)
{
    B[pos][l]=-1; B[pos][r]=-2;
    if(l+2>r) return;
    int p=(r-l-1)/P[pos];
    for(int i=l+1; i<r; i++)
    {
        B[pos][i]=(i-l-1)/p+Q[pos-1]+1;
    }
    for(int i=l+1; i<r; i+=p) f(pos+1, i, i+p-1);
}

vector<vector<int>> devise_strategy(int N)
{
    f(1, 1, 5022);
    A[0][0]=0;
    A[0][1]=-1; A[0][5022]=-2;
    for(int i=2; i<=5021; i++) A[0][i]=B[1][i];
    for(int i=1; i<=8; i++)
    {
        for(int j=Q[i-1]+1; j<=Q[i]; j++)
        {
            int t=A[j][0]=i%2;
            for(int k=1; k<=5022; k++)
            {
                if(B[i][k]==-1)
                {
                    if(t) A[j][k]=-2;
                    else A[j][k]=-1;
                }
                else if(B[i][k]==-2)
                {
                    if(t) A[j][k]=-1;
                    else A[j][k]=-2;
                }
                else if(B[i][k]<j)
                {
                    if(t) A[j][k]=-2;
                    else A[j][k]=-1;
                }
                else if(B[i][k]>j)
                {
                    if(t) A[j][k]=-1;
                    else A[j][k]=-2;
                }
                else
                {
                    if(B[i+1][k]==-1)
                    {
                        if(t) A[j][k]=-2;
                        else A[j][k]=-1;
                    }
                    else if(B[i+1][k]==-2)
                    {
                        if(t) A[j][k]=-1;
                        else A[j][k]=-2;
                    }
                    else A[j][k]=B[i+1][k];
                }
            }
        }
    }

    vector<vector<int>> ans=vector<vector<int>>(21, vector<int>(N+1));
    for(int i=0; i<=20; i++) for(int j=0; j<=N; j++) ans[i][j]=A[i][j];
    return ans;
}